package com.theeviljames.sorting;

import java.util.Arrays;

public class MergeSort implements ISort {

	public int[] sort(int[] A) {
		sort(A,0,A.length-1);
		return A;
	}

	private static void sort(int[] A, int i, int j){
		if(j>i){
			int mid = (i+j)/2;
			sort(A,i,mid);
			sort(A,mid+1,j);
			merge(A,i,mid,j);
		}
	}
	
	private static void merge(int[] A, int i, int mid, int j){
		int n1 = mid-i;
		int n2 = j-mid+1;
		int[] L = new int[n1+1];
		int[] R = new int[n2+1];
		for(int n = 0; n < n1; n++)L[n] = A[i+n];
		for(int m = 0; m < n2; m++)R[m] = A[mid+m];
		L[n1] = Integer.MAX_VALUE;
		R[n2] = Integer.MAX_VALUE;
		//System.out.println("L>"+ Arrays.toString(L));
		//System.out.println("R>"+ Arrays.toString(R));
		int n = 0;
		int m = 0;
		for(int p = i; p <= j; p++){
			if(L[n]<R[m]){
				A[p]=L[n++];
			}
			else{
				A[p]=R[m++];
			}
		}
		/*int[] c = new int[a.length+b.length];
		int j = 0; 
		int k =0;
		for(int i = 0; i < c.length-1; i++){
			c[i] = (a[j]<b[k])?a[j++]:b[k++];
		}
		c[c.length-1] = (j==a.length-1)?a[j]:b[k];
		return c;*/
	}
	
	@Override
	public String toString() {
		return "Merge Sort";
	}
	
	public static void main(String[] args) {
		int[] A = new int[]{1,3,5,2,4,6};
		sort(A, 0, A.length-1);
		System.out.println(Arrays.toString(A));
	}
}
